#include <stdio.h>
#include <stdlib.h>

#define null 0

/**
 * 栈的链式存储实现
 * 栈的特点：先进后出
 * */
typedef struct SNode *Stack;
struct SNode{
    int Data;
    struct SNode *Next;
};

Stack createStack();
int isEmpty(Stack s);
void push(int item, Stack s);
int pop(Stack s);
void show(Stack s);
int count(Stack s);

int main(){
    Stack s = createStack();
    push(1,s);
    push(2,s);
    push(3,s);
    pop(s);
    pop(s);
    show(s);
    // printf("count = %d", count(s));;
    return 0;
}

Stack createStack(){
    Stack s = (Stack)malloc(sizeof(struct SNode));
    s->Data = -1;
    s->Next = NULL;
    return s;
}

int isEmpty(Stack s){
    return (s->Next == NULL);
}

void push(int item, Stack s){
    //将元素item压入堆栈s
    struct SNode *TmpCell;
    TmpCell = (Stack)malloc(sizeof(struct SNode));
    //注意：这里s可理解为哨兵结点（不保存数据的首节点），入栈相当于插入到哨兵节点之后
    TmpCell->Data = item;
    TmpCell->Next = s->Next;
    s->Next = TmpCell;
}

int pop(Stack s){
    //删除并返回堆栈s的栈顶元素
    struct SNode *FirstCell;
    int TopElem;
    if(isEmpty(s)){
        printf("堆栈为空");
        return null;
    }else{
        FirstCell = s->Next;
        s->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

void show(Stack s){
    printf("stack:");
    while(s->Next!=NULL){
        printf(" %d ", s->Next->Data);
        //关键点：打印一个结点后将指针向后移一位
        s->Next = s->Next->Next;
    }
}

int count(Stack s){
    int counts = 0;
    while(s->Next!=NULL){
        counts++;
        if(counts == 100){
            return counts;
        }
    }
    return counts;
}
